{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Escape the Spreading Fire"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #binary-search #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #二分查找 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumMinutes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #逃离火灾"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始大小为 <code>m x n</code>&nbsp;的二维整数数组&nbsp;<code>grid</code>&nbsp;，它表示一个网格图。每个格子为下面 3 个值之一：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0</code> 表示草地。</li>\n",
    "\t<li><code>1</code> 表示着火的格子。</li>\n",
    "\t<li><code>2</code>&nbsp;表示一座墙，你跟火都不能通过这个格子。</li>\n",
    "</ul>\n",
    "\n",
    "<p>一开始你在最左上角的格子&nbsp;<code>(0, 0)</code>&nbsp;，你想要到达最右下角的安全屋格子&nbsp;<code>(m - 1, n - 1)</code>&nbsp;。每一分钟，你可以移动到&nbsp;<strong>相邻</strong>&nbsp;的草地格子。每次你移动 <strong>之后</strong>&nbsp;，着火的格子会扩散到所有不是墙的 <strong>相邻</strong>&nbsp;格子。</p>\n",
    "\n",
    "<p>请你返回你在初始位置可以停留的 <strong>最多 </strong>分钟数，且停留完这段时间后你还能安全到达安全屋。如果无法实现，请你返回 <code>-1</code>&nbsp;。如果不管你在初始位置停留多久，你 <strong>总是</strong>&nbsp;能到达安全屋，请你返回&nbsp;<code>10<sup>9</sup></code>&nbsp;。</p>\n",
    "\n",
    "<p>注意，如果你到达安全屋后，火马上到了安全屋，这视为你能够安全到达安全屋。</p>\n",
    "\n",
    "<p>如果两个格子有共同边，那么它们为 <strong>相邻</strong>&nbsp;格子。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/10/ex1new.jpg\" style=\"width: 650px; height: 404px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>grid = [[0,2,0,0,0,0,0],[0,0,0,2,2,1,0],[0,2,0,0,1,2,0],[0,0,2,2,2,0,2],[0,0,0,0,0,0,0]]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>上图展示了你在初始位置停留 3 分钟后的情形。\n",
    "你仍然可以安全到达安全屋。\n",
    "停留超过 3 分钟会让你无法安全到达安全屋。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/10/ex2new2.jpg\" style=\"width: 515px; height: 150px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>grid = [[0,0,0,0],[0,1,2,0],[0,2,0,0]]\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>上图展示了你马上开始朝安全屋移动的情形。\n",
    "火会蔓延到你可以移动的所有格子，所以无法安全到达安全屋。\n",
    "所以返回 -1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/10/ex3new.jpg\" style=\"width: 174px; height: 150px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>grid = [[0,0,0],[2,2,0],[1,2,0]]\n",
    "<b>输出：</b>1000000000\n",
    "<b>解释：</b>上图展示了初始网格图。\n",
    "注意，由于火被墙围了起来，所以无论如何你都能安全到达安全屋。\n",
    "所以返回 10<sup>9</sup> 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>2 &lt;= m, n &lt;= 300</code></li>\n",
    "\t<li><code>4 &lt;= m * n &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>grid[i][j]</code>&nbsp;是&nbsp;<code>0</code>&nbsp;，<code>1</code>&nbsp;或者&nbsp;<code>2</code>&nbsp;。</li>\n",
    "\t<li><code>grid[0][0] == grid[m - 1][n - 1] == 0</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [escape-the-spreading-fire](https://leetcode.cn/problems/escape-the-spreading-fire/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [escape-the-spreading-fire](https://leetcode.cn/problems/escape-the-spreading-fire/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,2,0,0,0,0,0],[0,0,0,2,2,1,0],[0,2,0,0,1,2,0],[0,0,2,2,2,0,2],[0,0,0,0,0,0,0]]', '[[0,0,0,0],[0,1,2,0],[0,2,0,0]]', '[[0,0,0],[2,2,0],[1,2,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bfs(self, grid, queue, time, m, n):\n",
    "        d = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        while queue:\n",
    "            x, y, t = queue.popleft()\n",
    "            time[x][y] = t\n",
    "            for i, j in d: # directions\n",
    "                ii, jj = x + i, y + j\n",
    "                if 0 <= ii < m and 0 <= jj < n and grid[ii][jj] == 0 and time[ii][jj] == -1: # in the grid, it's grass, I have not reached this cell\n",
    "                    queue.append((ii, jj, t + 1)) # minute + 1\n",
    "\n",
    "    def maximumMinutes(self, grid: List[List[int]]) -> int:\n",
    "        # I move first and then fire spread\n",
    "        # I - grass - 4 directions\n",
    "        # fire - grass - 4 directions\n",
    "        # output: 1) impossible: -1; 2) always possible: 10**9; 3) the maximum number of minutes\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "\n",
    "        me = [[-1] * n  for _ in range(m)] # store the minutes for me to reach a specific cell\n",
    "        fire = [[-1] * n for _ in range(m)] # store the minutes for fire to reach a specific cell\n",
    "\n",
    "        # BFS for me - change the value in the list of me\n",
    "        me_queue = deque([(0, 0, 0)]) # x, y, minutes\n",
    "        self.bfs(grid, me_queue, me, m, n)\n",
    "        \n",
    "        # BFS for fire - change the value in the list of fire\n",
    "        fire_queue = deque([(x, y, 0) for x in range(m) for y in range(n) if grid[x][y] == 1])\n",
    "        self.bfs(grid, fire_queue, fire, m, n)\n",
    "\n",
    "        # check the arrival minutes of the bottom-right cell\n",
    "        me_t = me[-1][-1]\n",
    "        fire_t = fire[-1][-1]\n",
    "\n",
    "        # edges cases\n",
    "        if me_t == -1: return -1 # i cannot reach this cell\n",
    "        if fire_t == -1: return 10 ** 9 # the fire cannot reach this cell\n",
    "        if fire_t < me_t: return -1 # the fire runs faster than me, I cannot survive!\n",
    "\n",
    "        diff = fire_t - me_t\n",
    "        me_t1, me_t2 = me[-1][-2], me[-2][-1] # from left, from upper\n",
    "        fire_t1, fire_t2 = fire[-1][-2], fire[-2][-1]\n",
    "        if me_t1 > -1 and me_t2 > -1 and (fire_t1 - me_t1 > diff or fire_t2 - me_t2 > diff): # me and fire are from two differnet directions\n",
    "            return diff\n",
    "        return diff - 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinutes(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        \n",
    "        d = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "        def bfs(q):\n",
    "            time = [[-1]*n for _ in range(m)]\n",
    "            for i, j in q:\n",
    "                time[i][j] = 0\n",
    "            while q:\n",
    "                i, j = q.popleft()\n",
    "                for dx, dy in d:\n",
    "                    x = i+dx\n",
    "                    y = j+dy\n",
    "                    if x >= 0 and y >= 0 and x < m and y < n and grid[x][y] == 0 and time[x][y] == -1:\n",
    "                        time[x][y] = time[i][j]+1\n",
    "                        q.append((x, y))\n",
    "\n",
    "            return time[-1][-1], time[-1][-2], time[-2][-1]\n",
    "\n",
    "        q1 = deque([(0, 0)])\n",
    "        q2 = deque([])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    q2.append((i, j))\n",
    "\n",
    "        m1, m2, m3 = bfs(q1)\n",
    "        f1, f2, f3 = bfs(q2)\n",
    "\n",
    "        if m1 < 0:\n",
    "            return -1\n",
    "        if f1 < 0:\n",
    "            return 10**9\n",
    "        ans = f1-m1\n",
    "        if ans < 0:\n",
    "            return -1\n",
    "        # 同一个方向到达\n",
    "        if m2 < 0 or m3 < 0 or f2-m2 == f3-m3 == ans:\n",
    "            return ans-1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = {0: (1, 0), 1: (0, 1), 2: (0, -1), 3: (-1, 0)}\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinutes(self, grid: list[list[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = deque([])\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v == 2:\n",
    "                    grid[i][j] = -1\n",
    "                elif v == 1:\n",
    "                    grid[i][j] = 0\n",
    "                    f.append((i, j, 0))\n",
    "                else:\n",
    "                    grid[i][j] = inf\n",
    "        while f:\n",
    "            x, y, d = f.popleft()\n",
    "            for k in range(4):\n",
    "                nx, ny = x + DIRS[k][0], y + DIRS[k][1]\n",
    "                if m > nx >= 0 <= ny < n and grid[nx][ny] == inf:\n",
    "                    grid[nx][ny] = d + 1\n",
    "                    f.append((nx, ny, d + 1))\n",
    "        grid[-1][-1] += 1\n",
    "\n",
    "        q = deque([(0, 0, 0, int(1e9))])\n",
    "        ret = -1\n",
    "        while q:\n",
    "            x, y, d, ans = q.popleft()\n",
    "            if grid[x][y] == -1: continue\n",
    "            grid[x][y] = -1\n",
    "            for k in range(4):\n",
    "                nx, ny = x + DIRS[k][0], y + DIRS[k][1]\n",
    "                if m > nx >= 0 <= ny < n and grid[nx][ny] > d + 1:\n",
    "                    if (nx, ny) == (m - 1, n - 1):\n",
    "                        ret = max(ret, min(ans, grid[nx][ny] - d - 2))\n",
    "                    else:\n",
    "                        q.append((nx, ny, d + 1, min(ans, grid[nx][ny] - d - 2)))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://space.bilibili.com/206214\n",
    "class Solution:\n",
    "    def maximumMinutes(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def bfs(q: List[Tuple[int, int]]) -> (int, int, int):\n",
    "            time = [[-1] * n for _ in range(m)]\n",
    "            for i, j in q:\n",
    "                time[i][j] = 0\n",
    "            t = 1\n",
    "            while q:\n",
    "                tmp = q\n",
    "                q = []\n",
    "                for i, j in tmp:\n",
    "                    for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):\n",
    "                        if 0 <= x < m and 0 <= y < n and grid[x][y] == 0 and time[x][y] < 0:\n",
    "                            time[x][y] = t\n",
    "                            q.append((x, y))\n",
    "                t += 1\n",
    "            return time[-1][-1], time[-1][-2], time[-2][-1]\n",
    "\n",
    "        man_to_house_time, m1, m2 = bfs([(0, 0)])\n",
    "        if man_to_house_time < 0: return -1  # 人无法到终点\n",
    "        fire_to_house_time, f1, f2 = bfs([(i, j) for i, row in enumerate(grid) for j, v in enumerate(row) if v == 1])\n",
    "        if fire_to_house_time < 0: return 10 ** 9  # 火无法到终点\n",
    "        ans = fire_to_house_time - man_to_house_time\n",
    "        if ans < 0: return -1  # 火比人先到终点\n",
    "        if m1 < 0 or m2 < 0 or f1 - m1 == f2 - m2 == ans:\n",
    "            return ans - 1  # 火只会跟在人的后面，在到达终点前，人和火不能重合\n",
    "        return ans  # 人和火可以同时到终点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinutes(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def bfs(q: List[Tuple[int, int]]) -> (int, int, int):\n",
    "            time = [[-1] * n for _ in range(m)]\n",
    "            t = 0\n",
    "            while q:\n",
    "                tmp = q\n",
    "                q = []\n",
    "                for i, j in tmp:\n",
    "                    time[i][j] = t\n",
    "                    for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):\n",
    "                        if 0 <= x < m and 0 <= y < n and grid[x][y] == 0 and time[x][y] < 0:\n",
    "                            q.append((x, y))\n",
    "                t += 1\n",
    "            return time[-1][-1], time[-1][-2], time[-2][-1]\n",
    "\n",
    "        man_to_house_time, m1, m2 = bfs([(0, 0)])\n",
    "        if man_to_house_time < 0: return -1  # 人无法到终点\n",
    "        fire_to_house_time, f1, f2 = bfs([(i, j) for i, row in enumerate(grid) for j, v in enumerate(row) if v == 1])\n",
    "        if fire_to_house_time < 0: return 10 ** 9  # 火无法到终点\n",
    "        ans = fire_to_house_time - man_to_house_time\n",
    "        if ans < 0: return -1  # 火比人先到终点\n",
    "        if m1 < 0 or m2 < 0 or f1 - m1 == f2 - m2 == ans:\n",
    "            return ans - 1  # 火只会跟在人的后面，在到达终点前，人和火不能重合\n",
    "        return ans  # 人和火可以同时到终点\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/escape-the-spreading-fire/solutions/1460794/er-fen-bfspythonjavacgo-by-endlesscheng-ypp1/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "import time\n",
    "class Solution:\n",
    "    def maximumMinutes(self,grid):\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        def update_fire(init_fire,real_time_status):\n",
    "            counts = len(init_fire)\n",
    "            while counts:\n",
    "                x,y = init_fire.pop(0)\n",
    "                counts -= 1\n",
    "                if y - 1 >= 0 and real_time_status[x][y-1] not in [1,2]:\n",
    "                    real_time_status[x][y-1] = 1\n",
    "                    init_fire.append((x,y-1))\n",
    "                if y + 1 < len(real_time_status[0]) and real_time_status[x][y+1] not in [1,2]:\n",
    "                    real_time_status[x][y+1] = 1\n",
    "                    init_fire.append((x,y+1))\n",
    "                if x - 1 >= 0 and real_time_status[x-1][y] not in [1,2]:\n",
    "                    real_time_status[x-1][y] = 1\n",
    "                    init_fire.append((x-1,y))\n",
    "                if x + 1 < len(real_time_status) and real_time_status[x+1][y] not in [1,2]:\n",
    "                    real_time_status[x+1][y] = 1\n",
    "                    init_fire.append((x+1,y))\n",
    "\n",
    "        def can_pass(mins):\n",
    "            init_fire = []\n",
    "            root = [(0,0)]\n",
    "            for i in range(len(grid)):\n",
    "                for j in range(len(grid[0])):\n",
    "                    if grid[i][j] == 1:\n",
    "                        init_fire.append((i,j))\n",
    "            real_time_status = copy.deepcopy(grid[:])\n",
    "            for i in range(mins):\n",
    "                update_fire(init_fire,real_time_status)\n",
    "            while root:\n",
    "                counts = len(root)\n",
    "                while counts:\n",
    "                    x,y = root.pop(0)\n",
    "                    counts -= 1\n",
    "                    if real_time_status[x][y] == 1:\n",
    "                        continue\n",
    "                    if y - 1 >= 0 and real_time_status[x][y-1] == 0:\n",
    "                        real_time_status[x][y-1] = 3\n",
    "                        root.append((x,y-1))\n",
    "                    if y + 1 < len(real_time_status[0]) and real_time_status[x][y+1] == 0:\n",
    "                        real_time_status[x][y+1] = 3\n",
    "                        root.append((x,y+1))\n",
    "                    if x - 1 >= 0 and real_time_status[x-1][y] == 0:\n",
    "                        real_time_status[x-1][y] = 3\n",
    "                        root.append((x-1,y))\n",
    "                    if x + 1 < len(real_time_status) and real_time_status[x+1][y] == 0:\n",
    "                        real_time_status[x+1][y] = 3\n",
    "                        root.append((x+1,y))\n",
    "                    if (m-1,n-1) in root and real_time_status[-1][-1] != 1:\n",
    "                        return True\n",
    "                update_fire(init_fire,real_time_status)\n",
    "            return False\n",
    "        l,r = 0,m*n\n",
    "        while l <= r:\n",
    "            mid = (l+r)//2\n",
    "\n",
    "            if can_pass(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        if r == m*n:\n",
    "            return 10**9\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAX_MINUTES = 1000000000   # 最大分钟数\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinutes(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        fire_arrived = [[0] * n for _ in range(m)]        # 记录每个格子最早着火时间，如果为MAX_MINUTES表示不会着火\n",
    "        queue = []  # 用于广度优先搜索的队列\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, g in enumerate(row):\n",
    "                if g == 1:\n",
    "                    queue.append(i * n + j)     # 将初始着火的格子入队，并且其着火时间为0\n",
    "                else:\n",
    "                    fire_arrived[i][j] = MAX_MINUTES    # 其他格子初始为MAX_MINUTES\n",
    "        # 搜索每个格子，计算最早着火时间\n",
    "        while queue:\n",
    "            pos = queue.pop(0)\n",
    "            r, c = divmod(pos, n)\n",
    "            # 搜索四个方向：1.保证索引不越界；2.保证位置可达（草地）；3.保证位置未搜索过；\n",
    "            if r - 1 >= 0 and grid[r-1][c] == 0 and fire_arrived[r-1][c] == MAX_MINUTES:\n",
    "                fire_arrived[r-1][c] = fire_arrived[r][c] + 1\n",
    "                queue.append((r-1) * n + c)\n",
    "            if r + 1 < m and grid[r+1][c] == 0 and fire_arrived[r+1][c] == MAX_MINUTES:\n",
    "                fire_arrived[r+1][c] = fire_arrived[r][c] + 1\n",
    "                queue.append((r+1) * n + c)\n",
    "            if c - 1 >= 0 and grid[r][c-1] == 0 and fire_arrived[r][c-1] == MAX_MINUTES:\n",
    "                fire_arrived[r][c-1] = fire_arrived[r][c] + 1\n",
    "                queue.append(r*n+c-1)\n",
    "            if c + 1 < n and grid[r][c+1] == 0 and fire_arrived[r][c+1] == MAX_MINUTES:\n",
    "                fire_arrived[r][c+1] = fire_arrived[r][c] + 1\n",
    "                queue.append(r*n+c+1)\n",
    "        \n",
    "        person_arrived = [[MAX_MINUTES] * n for _ in range(m)]  # 人到达每个格子的最早时间；每个位置初始化，MAX_MINUTES表示不可达\n",
    "        person_arrived[0][0] = 0    # 起点时间初始为0\n",
    "        res = -1   # 结果\n",
    "        queue.append(0) # 起点入队\n",
    "        while queue:\n",
    "            pos = queue.pop(0)\n",
    "            r, c = divmod(pos, n)\n",
    "            if r == m - 1 and c == n - 1:\n",
    "                # 到达终点，更新结果\n",
    "                res = min(fire_arrived[m-1][n-1] - person_arrived[m-1][n-1],\n",
    "                        max(fire_arrived[m-1][n-2] - 1 - person_arrived[m-1][n-2], fire_arrived[m-2][n-1] - 1 - person_arrived[m-2][n-1]))\n",
    "                break  # 由于BFS保证到达终点的时间是最短的，因此到达终点即可退出了\n",
    "            # 人比火晚到这个位置，就到不了这个位置，更无法通过这个位置到达其他位置，因此跳过\n",
    "            if person_arrived[r][c] >=  fire_arrived[r][c]: continue\n",
    "            # 搜索四个方向：1.保证索引不越界；2.保证位置可达（草地）；3.保证位置未搜索过；\n",
    "            if r - 1 >= 0 and grid[r-1][c] == 0 and person_arrived[r-1][c] == MAX_MINUTES:\n",
    "                person_arrived[r-1][c] = person_arrived[r][c] + 1\n",
    "                queue.append((r-1) * n + c)\n",
    "            if r + 1 < m and grid[r+1][c] == 0 and person_arrived[r+1][c] == MAX_MINUTES:\n",
    "                person_arrived[r+1][c] = person_arrived[r][c] + 1\n",
    "                queue.append((r+1) * n + c)\n",
    "            if c - 1 >= 0 and grid[r][c-1] == 0 and person_arrived[r][c-1] == MAX_MINUTES:\n",
    "                person_arrived[r][c-1] = person_arrived[r][c] + 1\n",
    "                queue.append(r*n+c-1)\n",
    "            if c + 1 < n and grid[r][c+1] == 0 and person_arrived[r][c+1] == MAX_MINUTES:\n",
    "                person_arrived[r][c+1] = person_arrived[r][c] + 1\n",
    "                queue.append(r*n+c+1)\n",
    "        if res >= 0 and fire_arrived[m-1][n-1] == MAX_MINUTES: return MAX_MINUTES\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinutes(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        def bfs(q: List[Tuple[int, int]]) -> (int, int, int):\n",
    "            time = [[-1] * n for _ in range(m)]\n",
    "            for i, j in q:\n",
    "                time[i][j] = 0\n",
    "            t = 1\n",
    "            while q:\n",
    "                tmp = q\n",
    "                q = []\n",
    "                for i, j in tmp:\n",
    "                    for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):\n",
    "                        if 0 <= x < m and 0 <= y < n and grid[x][y] == 0 and time[x][y] < 0:\n",
    "                            time[x][y] = t\n",
    "                            q.append((x, y))\n",
    "                t += 1\n",
    "            return time[-1][-1], time[-1][-2], time[-2][-1]\n",
    "        \n",
    "        man_to_house_time, m1, m2 = bfs([(0, 0)])\n",
    "        if man_to_house_time < 0:\n",
    "            return -1\n",
    "        fire_pos = [(i, j) for i, row in enumerate(grid) for j, x in enumerate(row) if x == 1]\n",
    "        fire_to_house_time, f1, f2 = bfs(fire_pos)\n",
    "        if fire_to_house_time < 0:\n",
    "            return 10 ** 9\n",
    "        d = fire_to_house_time - man_to_house_time\n",
    "        if d < 0:\n",
    "            return -1\n",
    "        if (m1 != -1 and m1 + d < f1) or (m2 != -1 and m2 + d < f2):\n",
    "            return d\n",
    "        return d - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinutes(self, grid: List[List[int]]) -> int:\n",
    "        '''\n",
    "        总体思路：二分火势蔓延的时间，找到使得小人能到达终点的最长蔓延时间\n",
    "        :param grid: 环境现状\n",
    "        :return: 返回可停留时间\n",
    "        '''\n",
    "        # BFS 计算出火蔓延到该格子的时刻\n",
    "        def spread(grid: List[List[int]]) -> (List[List[int]], int):\n",
    "            '''\n",
    "            :param time: 蔓延时间\n",
    "            :param grid: 环境现状，这里我们重新约定一下标记, 当改点为-1时表示火永远蔓延不到，如果为-2时表示墙，grid[i][j] > 0 时表示 grid[i][j] 个时刻蔓延到\n",
    "            :return: 返回火势蔓延了多少格子\n",
    "            '''\n",
    "            m, n = len(grid), len(grid[0])\n",
    "            temp_grid = [[-1] * n for _ in range(m)]\n",
    "            fire_boundary = []  # 着火的边界点\n",
    "            time = 0  # 记录在哪个时间，火蔓延到哪了\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == 2:\n",
    "                        temp_grid[i][j] = -2\n",
    "                    elif grid[i][j] == 1:\n",
    "                        fire_boundary.append([i, j])\n",
    "                        temp_grid[i][j] = 0\n",
    "                    elif grid[i][j] == 0:\n",
    "                        temp_grid[i][j] = -1\n",
    "            while len(fire_boundary) > 0:\n",
    "                temp_fire_boundary = []\n",
    "                time += 1\n",
    "                \"\"\"\n",
    "                调试输出\n",
    "                \"\"\"\n",
    "                # print2Darray(temp_grid)\n",
    "                for i, j in fire_boundary:\n",
    "                    if i + 1 < m and temp_grid[i + 1][j] == -1:\n",
    "                        temp_fire_boundary.append([i + 1, j])\n",
    "                    if j + 1 < n and temp_grid[i][j + 1] == -1:\n",
    "                        temp_fire_boundary.append([i, j + 1])\n",
    "                    if i - 1 >= 0 and temp_grid[i - 1][j] == -1:\n",
    "                        temp_fire_boundary.append([i - 1, j])\n",
    "                    if j - 1 >= 0 and temp_grid[i][j - 1] == -1:\n",
    "                        temp_fire_boundary.append([i, j - 1])\n",
    "                # 更新火势蔓延点\n",
    "                for i, j in temp_fire_boundary:\n",
    "                    temp_grid[i][j] = time\n",
    "                fire_boundary = temp_fire_boundary\n",
    "            return temp_grid, time\n",
    "\n",
    "        # 广度搜索，计算能否逃脱,在逃脱时，还需同步模拟火势蔓延\n",
    "        def escape(time:int, grid: List[List[int]]) -> bool:\n",
    "            '''\n",
    "            :param time:    等待时间\n",
    "            :param grid:    环境现状\n",
    "            :return: 是否能逃脱\n",
    "            '''\n",
    "            m, n = len(grid), len(grid[0])\n",
    "            q = [[0, 0]]\n",
    "            # 如果等待时间超过了起始点着火的时刻，则一定不能逃脱\n",
    "            if grid[0][0] >= 0 and time > grid[0][0]:\n",
    "                return False\n",
    "            need_time = time\n",
    "            arrived = [[0] * n for _ in range(m)]\n",
    "            while len(q) > 0:\n",
    "                need_time += 1  # 之后再尝试寻找出路,所需时间+1\n",
    "                t = []\n",
    "                # 寻找可选路径，并检查是否到达终点\n",
    "                for i, j in q:\n",
    "                    # 否则寻找可选路径,只要在火蔓延之前到达该格子就没事\n",
    "                    for ii,jj in (i + 1, j),(i, j + 1),(i - 1, j),(i, j - 1):\n",
    "                        '''\n",
    "                        需要满足条件：\n",
    "                        1. 在边界区域内\n",
    "                        2. 没访问过\n",
    "                        3. 到达时刻在火焰蔓延时刻之前\n",
    "                        '''\n",
    "                        # 如果此时位置已经在安全屋了则返回True，即可以逃脱\n",
    "                        if (ii == m - 1 and jj == n - 1\n",
    "                                and (grid[ii][jj] == -1 or (need_time <= grid[ii][jj] and grid[ii][jj] >= 0))):\n",
    "                            return True\n",
    "                        if (ii < m and ii >=0 and jj < n and jj >= 0\n",
    "                                and arrived[ii][jj] == 0\n",
    "                                and (grid[ii][jj] == -1 or (need_time < grid[ii][jj] and grid[ii][jj] >= 0))):\n",
    "                            arrived[ii][jj] = -1  # 标记该位置已经走过\n",
    "                            t.append([ii, jj])\n",
    "                q = t\n",
    "            # 走不出去就返False\n",
    "            return False\n",
    "\n",
    "        # 使火势蔓延mid个时间,还要加上逃跑时间\n",
    "        temp_grid, time = spread(grid)\n",
    "        # print2Darray(temp_grid)\n",
    "        # 如果等待火势蔓延的最长时间都能通过的话，就表示总是能通过\n",
    "        if escape(time,temp_grid):\n",
    "            return int(1e9)\n",
    "        l, r = -1, time\n",
    "        while l + 1 != r:\n",
    "            mid = (l + r) // 2\n",
    "            # 检查是否可以逃脱，以调整允许蔓延时间\n",
    "            if not escape(mid, temp_grid):\n",
    "                # 要找到最长的允许蔓延时间，就需要确保，右边界永远是不可逃脱的时间\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinutes(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        fireTime = [[inf] * n for _ in range(m)]\n",
    "\n",
    "        def bfs():\n",
    "            q = []\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == 1:\n",
    "                        q.append((i, j))\n",
    "                        fireTime[i][j] = 0\n",
    "            \n",
    "            time = 1\n",
    "            while len(q) > 0:\n",
    "                tmp = q\n",
    "                q = []\n",
    "                for cx, cy in tmp:\n",
    "                    for nx, ny in (cx, cy - 1), (cx, cy + 1), (cx - 1, cy), (cx + 1, cy):\n",
    "                        if nx >= 0 and ny >= 0 and nx < m and ny < n:\n",
    "                            if grid[nx][ny] == 2 or fireTime[nx][ny] != inf:\n",
    "                                continue\n",
    "                            q.append((nx, ny))\n",
    "                            fireTime[nx][ny] = time\n",
    "                time += 1\n",
    "\n",
    "        def getArriveTime(stayTime):\n",
    "            visit = set((0, 0))\n",
    "            q = []\n",
    "            q.append((0, 0, stayTime))\n",
    "            while len(q) > 0:\n",
    "                tmp = q\n",
    "                q = []\n",
    "\n",
    "                for cx, cy, time in tmp:\n",
    "                    if cx == m - 1 and cy == n - 1:\n",
    "                        return True\n",
    "                    for nx, ny in (cx, cy - 1), (cx, cy + 1), (cx - 1, cy), (cx + 1, cy):\n",
    "                        if nx >= 0 and ny >= 0 and nx < m and ny < n:\n",
    "                            if (nx, ny) in visit or grid[nx][ny] == 2:\n",
    "                                continue\n",
    "                            # 到达安全屋\n",
    "                            if nx == m - 1 and ny == n - 1:\n",
    "                                return  time + 1\n",
    "                            # 火未到达当前位置 \n",
    "                            if fireTime[nx][ny] > time + 1:\n",
    "                                q.append((nx, ny, time + 1))\n",
    "                                visit.add((nx, ny))\n",
    "            return -1\n",
    "\n",
    "        # 通过 bfs 求出每个格子着火的时间\n",
    "        bfs()\n",
    "        # 找到起点到每个格子的最短路径\n",
    "        arriveTime = getArriveTime(0)\n",
    "        # 安全屋不可达\n",
    "        if arriveTime < 0:\n",
    "            return -1\n",
    "        # 火不会到达安全屋 \n",
    "        if fireTime[m - 1][n - 1] == inf:\n",
    "            return 10**9\n",
    "        ans = fireTime[m - 1][n - 1] - arriveTime\n",
    "        return ans if getArriveTime(ans) >= 0 else ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinutes(self, grid: List[List[int]]) -> int:\n",
    "        def bfs():\n",
    "            m, n = len(grid), len(grid[0])\n",
    "            q = []\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == 1:\n",
    "                        q.append((i, j))\n",
    "                        fireTime[i][j] = 0\n",
    "            \n",
    "            time = 1\n",
    "            while len(q) > 0:\n",
    "                tmp = q\n",
    "                q = []\n",
    "                for cx, cy in tmp:\n",
    "                    for nx, ny in (cx, cy - 1), (cx, cy + 1), (cx - 1, cy), (cx + 1, cy):\n",
    "                        if nx >= 0 and ny >= 0 and nx < m and ny < n:\n",
    "                            if grid[nx][ny] == 2 or fireTime[nx][ny] != inf:\n",
    "                                continue\n",
    "                            q.append((nx, ny))\n",
    "                            fireTime[nx][ny] = time\n",
    "                time += 1\n",
    "\n",
    "        def check(stayTime):\n",
    "            print(stayTime)\n",
    "            m, n = len(grid), len(grid[0])\n",
    "            visit = set((0, 0))\n",
    "            q = []\n",
    "            q.append((0, 0, stayTime))\n",
    "            while len(q) > 0:\n",
    "                tmp = q\n",
    "                q = []\n",
    "\n",
    "                for cx, cy, time in tmp:\n",
    "                    for nx, ny in (cx, cy - 1), (cx, cy + 1), (cx - 1, cy), (cx + 1, cy):\n",
    "                        if nx >= 0 and ny >= 0 and nx < m and ny < n:\n",
    "                            if (nx, ny) in visit or grid[nx][ny] == 2:\n",
    "                                continue\n",
    "                            # 到达安全屋\n",
    "                            if nx == m - 1 and ny == n - 1:\n",
    "                                return fireTime[nx][ny] >= time + 1\n",
    "                            # 火未到达当前位置 \n",
    "                            if fireTime[nx][ny] > time + 1:\n",
    "                                q.append((nx, ny, time + 1))\n",
    "                                visit.add((nx, ny))\n",
    "            return False\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        fireTime = [[inf] * n for _ in range(m)]\n",
    "        # 通过 bfs 求出每个格子着火的时间\n",
    "        bfs()\n",
    "        # 二分查找找到最大停留时间\n",
    "        ans = -1\n",
    "        low, high = 0, m * n\n",
    "        while low <= high:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid - 1\n",
    "        return ans if ans < m * n else 10**9\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "move = [[-1,0],[1,0],[0,-1],[0,1]]\n",
    "class Solution:\n",
    "    # 判断当前grid情况下能否顺利到达终点\n",
    "    def checkRoad(self, grid) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        nowx = nowy = 0\n",
    "        # Queue代表人，Queue2代表火焰，Vis同理\n",
    "        Queue = []\n",
    "        Queue2 = []\n",
    "        Vis = [[0 for j in range(len(grid[0]))] for i in range(len(grid))]\n",
    "        Vis2 = [[0 for j in range(len(grid[0]))] for i in range(len(grid))]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    Queue2.append((i, j))\n",
    "                    Vis2[i][j] = 1\n",
    "        Vis[0][0] = 1\n",
    "        Queue.append((nowx, nowy))\n",
    "        while len(Queue) > 0:\n",
    "           # curstep控制人的出队次数，保证出队元素都是当前时间下走到的\n",
    "            curstep = len(Queue)\n",
    "            while curstep > 0:\n",
    "                curstep -= 1\n",
    "                nowx, nowy = Queue[0]\n",
    "                del Queue[0]\n",
    "                if nowx == m - 1 and nowy == n - 1:\n",
    "                    return True\n",
    "                if grid[nowx][nowy] == 1:\n",
    "                    continue\n",
    "                for i in move:\n",
    "                    nextx = nowx + i[0]\n",
    "                    nexty = nowy + i[1]\n",
    "                    if nextx < 0 or nextx >= m or nexty < 0 or nexty >= n:\n",
    "                        continue\n",
    "                    if Vis[nextx][nexty] == 1:\n",
    "                        continue\n",
    "                    if grid[nextx][nexty] == 0:\n",
    "                        Vis[nextx][nexty] = 1\n",
    "                        Queue.append((nextx, nexty))\n",
    "            # maxstep空值火焰出队次数，保证火焰到达的地方都是当前时间到达的\n",
    "            maxstep = len(Queue2)\n",
    "            while maxstep > 0:\n",
    "                maxstep -= 1\n",
    "                nowx2, nowy2 = Queue2[0]\n",
    "                del Queue2[0]\n",
    "                for i in move:\n",
    "                    nextx2 = nowx2 + i[0]\n",
    "                    nexty2 = nowy2 + i[1]\n",
    "                    if nextx2 < 0 or nextx2 >= m or nexty2 < 0 or nexty2 >= n:\n",
    "                        continue\n",
    "                    if Vis2[nextx2][nexty2] == 1:\n",
    "                        continue\n",
    "                    if grid[nextx2][nexty2] == 0:\n",
    "                        Vis2[nextx2][nexty2] = 1\n",
    "                        grid[nextx2][nexty2] = 1\n",
    "                        Queue2.append((nextx2, nexty2))\n",
    "        return False\n",
    "\n",
    "    # 判断step的时间内是否可以顺利到达终点\n",
    "    def canArrive(self, grid, step) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        vis = [[0 for j in range(len(grid[0]))] for i in range(len(grid))]\n",
    "        nowStep = startx = starty = 0\n",
    "        queue = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    queue.append((i, j))\n",
    "                    vis[i][j] = 1\n",
    "        while nowStep < step:\n",
    "            nowStep += 1\n",
    "            # 火焰队列没有元素且可达终点，就可以等待任意时间\n",
    "            if len(queue) == 0:\n",
    "                if self.checkRoad(grid) == True:\n",
    "                    return 1000000000\n",
    "                else:\n",
    "                    return 0\n",
    "            # N控制出队次数，防止新加入的火焰在这一时间扩散\n",
    "            N = len(queue)\n",
    "            for i in range(N):\n",
    "                nowx, nowy = queue[0]\n",
    "                del queue[0]\n",
    "                if nowx == 0 and nowy == 0:\n",
    "                    return 0\n",
    "                for i in move:\n",
    "                    nextx = nowx + i[0]\n",
    "                    nexty = nowy + i[1]\n",
    "                    if nextx < 0 or nextx >= m or nexty < 0 or nexty >= n:\n",
    "                        continue\n",
    "                    if vis[nextx][nexty] == 1:\n",
    "                        continue\n",
    "                    if grid[nextx][nexty] == 0:\n",
    "                        grid[nextx][nexty] = 1\n",
    "                        vis[nextx][nexty] = 1\n",
    "                        queue.append((nextx, nexty))\n",
    "        if self.checkRoad(grid) == True:\n",
    "            return 1\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "\n",
    "    def maximumMinutes(self, grid) -> int:\n",
    "        originMap = [[0 for j in range(len(grid[0]))] for i in range(len(grid))]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                originMap[i][j] = grid[i][j]\n",
    "        # 二分答案，注意判断0的情况\n",
    "        L = 0\n",
    "        R = len(grid) * len(grid[0]) + 1\n",
    "        # 一开始就无法到达终点\n",
    "        if self.checkRoad(grid) == False:\n",
    "            return -1\n",
    "        ans = -1\n",
    "        while L <= R:\n",
    "            for i in range(len(grid)):\n",
    "                for j in range(len(grid[0])):\n",
    "                    grid[i][j] = originMap[i][j]\n",
    "            mid = (L + R) >> 1\n",
    "            if mid == 0:\n",
    "                ans = mid\n",
    "                break\n",
    "            nowflag = self.canArrive(grid,mid)\n",
    "            if nowflag == 1:\n",
    "                ans = mid\n",
    "                L = mid + 1\n",
    "            elif nowflag == 0:\n",
    "                R = mid - 1\n",
    "            else:\n",
    "                ans = nowflag\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinutes(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        import heapq as hq\n",
    "\n",
    "        big_num = 1000000001\n",
    "\n",
    "        def getKey(x, y):\n",
    "            return f'{x}_{y}'\n",
    "\n",
    "        def withinBound(x, y):\n",
    "            return 0 <= x < len(grid) and 0 <= y < len(grid[x])\n",
    "\n",
    "        def getFireReachTime(_grid: List[List[int]]):\n",
    "            nonlocal big_num\n",
    "            fire_reach_time = []\n",
    "            need_search = deque()\n",
    "            for x in range(len(_grid)):\n",
    "                fire_reach_time.append([])\n",
    "                for y in range(len(_grid[x])):\n",
    "                    if _grid[x][y] == 0:  # 草地\n",
    "                        fire_reach_time[-1].append(big_num)\n",
    "                    elif _grid[x][y] == 1:  # 火\n",
    "                        fire_reach_time[-1].append(0)\n",
    "                        need_search.append((x, y, 0))\n",
    "                    else:  # 墙\n",
    "                        fire_reach_time[-1].append(-1)\n",
    "\n",
    "            searched = set()\n",
    "            while need_search:\n",
    "                x, y, time = need_search.popleft()\n",
    "                searched.add(getKey(x, y))\n",
    "                fire_reach_time[x][y] = time\n",
    "                for dx, dy in ((-1, 0), (1, 0), (0, 1), (0, -1)):\n",
    "                    if withinBound(x+dx, y+dy) and getKey(x+dx, y+dy) not in searched and grid[x+dx][y+dy] == 0:\n",
    "                        need_search.append((x+dx, y+dy, time+1))\n",
    "            return fire_reach_time\n",
    "\n",
    "        def getFireSpreadEndTime(_fire_reach_time: List[List[int]]):\n",
    "            nonlocal big_num\n",
    "            end_time = 0\n",
    "            for x in range(len(_fire_reach_time)):\n",
    "                for y in range(len(_fire_reach_time[x])):\n",
    "                    if _fire_reach_time[x][y] != big_num and _fire_reach_time[x][y] > end_time:\n",
    "                        end_time = _fire_reach_time[x][y]\n",
    "            return end_time\n",
    "\n",
    "        fire_reach_time = getFireReachTime(grid)\n",
    "        # print(fire_reach_time)\n",
    "\n",
    "        def distance(x1, y1, x2, y2):\n",
    "            return abs(x1-x2) + abs(y1-y2)\n",
    "\n",
    "        def canEscape(_time):\n",
    "            need_search = [(_time, 0, 0, _time)]\n",
    "            searched = set()\n",
    "            while need_search:\n",
    "                __weight, x, y, time = hq.heappop(need_search)\n",
    "                key = getKey(x, y)\n",
    "                # print(x, y, need_search)\n",
    "                if key in searched:\n",
    "                    continue\n",
    "                searched.add(key)\n",
    "                # print(x, y, need_search, searched)\n",
    "                x_target = len(grid) - 1\n",
    "                y_target = len(grid[x]) - 1\n",
    "                if x == x_target and y == y_target and fire_reach_time[x][y] >= time:\n",
    "                    return True\n",
    "                if fire_reach_time[x][y] <= time:\n",
    "                    continue\n",
    "                for dx, dy in ((-1, 0), (1, 0), (0, 1), (0, -1)):\n",
    "                    # print(x+dx, y+dy)\n",
    "                    if withinBound(x+dx, y+dy) and getKey(x+dx, y+dy) not in searched and grid[x+dx][y+dy] == 0:\n",
    "                        # print(x+dx, y+dy, 22)\n",
    "                        hq.heappush(need_search, (time + distance(x, y, x_target, y_target), x+dx, y+dy, time+1))\n",
    "            return False\n",
    "\n",
    "        end_time = getFireSpreadEndTime(fire_reach_time)\n",
    "\n",
    "        if canEscape(end_time):\n",
    "            return 10**9\n",
    "        if not canEscape(0):\n",
    "            return -1\n",
    "\n",
    "        l = 0\n",
    "        r = end_time\n",
    "        m = (l + r) // 2\n",
    "        while m > l:\n",
    "            if canEscape(m):\n",
    "                l = m\n",
    "            else:\n",
    "                r = m\n",
    "            m = (l + r) // 2\n",
    "        return m\n",
    "\n",
    "        # print(canEscape(0, set(), 0, 0))\n",
    "        # print(canEscape(1, set(), 0, 0))\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinutes(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        # 返回能否在初始位置停留 t 分钟，并安全到达安全屋\n",
    "        def check(t: int) -> bool:\n",
    "            f = [(i, j) for i, row in enumerate(grid) for j, x in enumerate(row) if x == 1]\n",
    "            on_fire = set(f)  # 标记着火的位置\n",
    "            def spread_fire():\n",
    "                # 火的 BFS\n",
    "                nonlocal f\n",
    "                tmp = f\n",
    "                f = []\n",
    "                for i, j in tmp:\n",
    "                    for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):  # 上下左右\n",
    "                        if 0 <= x < m and 0 <= y < n and grid[x][y] == 0 and (x, y) not in on_fire:\n",
    "                            on_fire.add((x, y))  # 标记着火的位置\n",
    "                            f.append((x, y))\n",
    "            while t and f:  # 如果火无法扩散就提前退出\n",
    "                spread_fire()  # 火扩散\n",
    "                t -= 1\n",
    "            if (0, 0) in on_fire:\n",
    "                return False  # 起点着火，寄\n",
    "\n",
    "            # 人的 BFS\n",
    "            q = [(0, 0)]\n",
    "            vis = set(q)\n",
    "            while q:\n",
    "                tmp = q\n",
    "                q = []\n",
    "                for i, j in tmp:\n",
    "                    if (i, j) in on_fire: continue  # 人走到这个位置后，火也扩散到了这个位置\n",
    "                    for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):  # 上下左右\n",
    "                        if 0 <= x < m and 0 <= y < n and grid[x][y] == 0 and (x, y) not in on_fire and (x, y) not in vis:\n",
    "                            if x == m - 1 and y == n - 1:\n",
    "                                return True  # 我们安全了…暂时。\n",
    "                            vis.add((x, y))  # 避免反复访问同一个位置\n",
    "                            q.append((x, y))\n",
    "                spread_fire()  # 火扩散\n",
    "            return False  # 人被火烧到，或者没有可以到达安全屋的路\n",
    "\n",
    "        # 这里我用开区间二分（其它写法也可以）\n",
    "        left = -1\n",
    "        right = m * n + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left if left < m * n else 10 ** 9\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinutes(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "\n",
    "        def check(t: int) -> bool:\n",
    "            f = [(i, j) for i, row in enumerate(grid) for j, x in enumerate(row) if x == 1]\n",
    "            on_fire = set(f)\n",
    "            def spread_fire():\n",
    "                nonlocal f\n",
    "                tmp = f\n",
    "                f = []\n",
    "                for i, j in tmp:\n",
    "                    for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):\n",
    "                        if 0 <= x < m and 0 <= y < n and grid[x][y] == 0 and (x, y) not in on_fire:\n",
    "                            on_fire.add((x, y))\n",
    "                            f.append((x, y))\n",
    "            while t and f:\n",
    "                spread_fire()\n",
    "                t -= 1\n",
    "            if (0, 0) in on_fire:\n",
    "                return False\n",
    "            q = [(0, 0)]\n",
    "            vis = set(q)\n",
    "            while q:\n",
    "                tmp = q\n",
    "                q = []\n",
    "                for i, j in tmp:\n",
    "                    if (i, j) in on_fire: continue\n",
    "                    for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):\n",
    "                        if 0 <= x < m and 0 <= y < n and grid[x][y] == 0 and (x, y) not in on_fire and (x, y) not in vis:\n",
    "                            if x == m - 1 and y == n - 1:\n",
    "                                return True\n",
    "                            vis.add((x, y))\n",
    "                            q.append((x, y))\n",
    "                spread_fire()\n",
    "            return False\n",
    "\n",
    "\n",
    "        left = -1\n",
    "        right = m * n + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left if left < m * n else 10 ** 9 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinutes(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        def check(t):\n",
    "            f=set()\n",
    "            for i in range(len(grid)):\n",
    "                for j in range(len(grid[0])):\n",
    "                    if grid[i][j]==1:\n",
    "                        f.add((i,j))\n",
    "            onfire=set(f)\n",
    "            while t and f:\n",
    "                tmp=f\n",
    "                f=[]\n",
    "                for i,j in tmp:\n",
    "                    for x,y in (i-1,j),(i+1,j),(i,j-1),(i,j+1):\n",
    "                        if m>x>=0 and n>y>=0 and grid[x][y]==0 and (x,y) not in onfire:\n",
    "                            onfire.add((x,y))\n",
    "                            f.append((x,y))\n",
    "                t-=1\n",
    "            if (0,0) in onfire:\n",
    "                return False\n",
    "            q=[(0,0)]\n",
    "            vis=set(q)\n",
    "            while q:\n",
    "                tmp=q\n",
    "                q=[]\n",
    "                for i,j in tmp:\n",
    "                    if(i,j) in onfire:continue\n",
    "                    for x,y in(i-1,j),(i+1,j),(i,j-1),(i,j+1):\n",
    "                        if 0<=x<m and 0<=y<n and grid[x][y]==0 and (x,y) not in onfire and (x,y) not in vis:\n",
    "                            if x==m-1 and y==n-1:\n",
    "                                return True\n",
    "                            q.append((x,y))\n",
    "                            vis.add((x,y))\n",
    "                tmp_f=f\n",
    "                f=[]\n",
    "                for i,j in tmp_f:\n",
    "                    if(i,j) in tmp_f:\n",
    "                        for x,y in(i-1,j),(i+1,j),(i,j-1),(i,j+1):\n",
    "                            if  0<=x<m and 0<=y<n and grid[x][y]==0 and (x,y) not in onfire:\n",
    "                                f.append((x,y))\n",
    "                                onfire.add((x,y))\n",
    "            return False\n",
    "        left,right=-1,m*n+1\n",
    "        while left+1<right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid):\n",
    "                left=mid\n",
    "            else:\n",
    "                right=mid\n",
    "        return left if left<m*n else 10**9\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinutes(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        def check(t):\n",
    "            f=set()\n",
    "            for i in range(len(grid)):\n",
    "                for j in range(len(grid[0])):\n",
    "                    if grid[i][j]==1:\n",
    "                        f.add((i,j))\n",
    "            onfire=set(f)\n",
    "            while t and f:\n",
    "                tmp=f\n",
    "                f=[]\n",
    "                for i,j in tmp:\n",
    "                    for x,y in (i-1,j),(i+1,j),(i,j-1),(i,j+1):\n",
    "                        if m>x>=0 and n>y>=0 and grid[x][y]==0 and (x,y) not in onfire:\n",
    "                            onfire.add((x,y))\n",
    "                            f.append((x,y))\n",
    "                t-=1\n",
    "            if (0,0) in onfire:\n",
    "                return False\n",
    "            q=[(0,0)]\n",
    "            vis=set(q)\n",
    "            while q:\n",
    "                tmp=q\n",
    "                q=[]\n",
    "                for i,j in tmp:\n",
    "                    if(i,j) in onfire:continue\n",
    "                    for x,y in(i-1,j),(i+1,j),(i,j-1),(i,j+1):\n",
    "                        if 0<=x<m and 0<=y<n and grid[x][y]==0 and (x,y) not in onfire and (x,y) not in vis:\n",
    "                            if x==m-1 and y==n-1:\n",
    "                                return True\n",
    "                            q.append((x,y))\n",
    "                            vis.add((x,y))\n",
    "                tmp_f=f\n",
    "                f=[]\n",
    "                for i,j in tmp_f:\n",
    "                    if(i,j) in tmp_f:\n",
    "                        for x,y in(i-1,j),(i+1,j),(i,j-1),(i,j+1):\n",
    "                            if  0<=x<m and 0<=y<n and grid[x][y]==0 and (x,y) not in onfire:\n",
    "                                f.append((x,y))\n",
    "                                onfire.add((x,y))\n",
    "            return False\n",
    "        left,right=0,m*n+1\n",
    "        while left<=right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid):\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid-1\n",
    "        return right if (right)<m*n else 10**9\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
